package lista;


@SuppressWarnings("rawtypes")
public class TLista implements ILista{
	
	public IElemento primero;
	public IElemento ultimo;
	public int cantElementos;
	
	/**
	 * Constructor de TLista
	 */
	public TLista (){
		this.primero = null;
		this.ultimo = null;
		this.cantElementos = 0;
	}

	/**
	 * Retorna el primer elemento de la lista
	 * @return Primer elemento de la lista
	 */
	@Override
	public IElemento obtenerPrimero() {
		return this.primero;
	}

	/**
	 * Retorna el ultimo elemento de la lista
	 * @return Ultimo elemento de la lista
	 */
	@Override
	public IElemento obtenerUltimo() {
		return this.ultimo;
	}

	/**
	 * Inserta en el comienzo de la lista el elemento unElemento
	 * @param unElemento Elemento a insertar
	 * @return Retorna true si se inserto el elemento, false en caso contrario
	 */
	@Override
	public boolean insertarAlPrincipio(IElemento unElemento) {
		if (unElemento != null) {
			if (this.esVacia()) {
				this.ultimo = unElemento;
			}
			unElemento.setSiguiente(this.primero);
			this.primero = unElemento;
			this.cantElementos++;
			return true;
		}
		else
			return false;
	}

	/**
	 * Inserta en el final de la lista el elemento unElemento
	 * @param unElemento Elemento a insertar
	 * @return Retorna true si se inserto el elemento, false en caso contrario
	 */
	@Override
	public boolean insertarAlFinal(IElemento unElemento) {
		if (unElemento != null) {
			if (this.esVacia()) {
				return this.insertarAlPrincipio(unElemento);
			} 
			else {
					unElemento.setSiguiente(null);
					this.ultimo.setSiguiente(unElemento);
					this.ultimo = unElemento;
					this.cantElementos++;
					return true;
			}
		} 
		else
			return false;
	}

	/**
	 * Retorna true si la lista es vacia, false en caso contrario
	 * @return true si la lista es vacia, false en caso contrario
	 */
	@Override
	public boolean esVacia() {
		return this.cantElementos == 0;
	}

	/**
	 * Busca si existe un elemento con etiqueta unaEtiqueta, si lo encuentra lo retorna, en caso contrario retorna null
	 * @param unaEtiqueta Etiqueta a buscar
	 * @return Elemento encontrado o null
	 */
	@Override
	public IElemento buscar(Comparable unaEtiqueta) {
		IElemento first = this.primero;
		return buscarRecursivo(first, unaEtiqueta);
	}
	
	/**
	 * Metodo auxiliar recursivo que busca en la lista si existe un elemento con etiqueta unaEtiqueta 
	 * @param first Primero de la lista
	 * @param unaEtiqueta Etiqueta a buscar
	 * @return Elemento encontrado o null
	 */
	public IElemento buscarRecursivo(IElemento first, Comparable unaEtiqueta){
		if (first == null)
			return null;
		else if (first.getEtiqueta().equals(unaEtiqueta))
			return first;
		else
			return (buscarRecursivo(first.getSiguiente(), unaEtiqueta));
	}

	/**
	 * Si existe, elimina el elemento con etiqueta unaEtiqueta y los retorna, en caso contrario retorna false
	 * @param Etiqueta a buscar
	 * @return Elemento eliminado o null
	 */
	@Override
	public IElemento eliminar(Comparable unaEtiqueta) {
		if (this.buscar(unaEtiqueta) == null) {
			return null;
		} 
		else if (this.cantElementos == 1) {
			IElemento elem = this.primero;
			this.primero = null;
			this.ultimo = null;
			this.cantElementos--;
			return elem;
		} 
		else {
				IElemento elem = null;
				IElemento nodo = this.primero;
				if (nodo.getEtiqueta().equals(unaEtiqueta)) {
					return quitarPrimero();
				} 
				else {
						while (!(nodo.getSiguiente().getEtiqueta().equals(unaEtiqueta))) {
							nodo = nodo.getSiguiente();
						}
						if (this.ultimo == nodo.getSiguiente()){
							this.ultimo = nodo;
						}
						elem = nodo.getSiguiente();
						nodo.setSiguiente(nodo.getSiguiente().getSiguiente());
						this.cantElementos--;
						return elem;
					}
			}
	}
	
	/**
	 * Retorna la cantidad de elementos de la lista
	 * @return cantidad de elementos de la lista
	 */
	@Override
	public int obtenerCantidadElementos() {
		return this.cantElementos;
	}

	/**
	 * Inserta en la lista de forma ordenada el elemento unElemento
	 * @param elemento a insertar
	 * @return true si lo inserto, false en caso contrario
	 */
	@SuppressWarnings({ "unchecked", "unused" })
	@Override
	public boolean insertarOrdenado(IElemento unElemento) {
		if (unElemento == null)
			return false;
		else {
				if (this.esVacia()) {
					return insertarAlPrincipio(unElemento);
				} 
				else {
						IElemento aux = primero;
						if (primero.getEtiqueta().compareTo(unElemento.getEtiqueta()) >= 0) {
							return insertarAlPrincipio(unElemento);
						} 
						else {
								while (aux.getSiguiente() != null && aux.getSiguiente().getEtiqueta().compareTo(unElemento.getEtiqueta()) <= 0) {
									aux = aux.getSiguiente();
								}
								if (aux == null)
									return insertarAlFinal(unElemento);
								else {
									unElemento.setSiguiente(aux.getSiguiente());
									aux.setSiguiente(unElemento);
									this.cantElementos++;
									return true;
								}
							}
					}
			}
	}

	/**
	 * Vacia la lista
	 */
	@Override
	public void vaciar() {
		this.primero = null;
		this.ultimo = null;
		this.cantElementos = 0;		
	}

	/**
	 * Retorna en un arreglo las etiquetas de la lista
	 * @return Arreglo de etiquetas
	 */
	@Override
	public Comparable[] etiquetasToArray() {
		int cantElementosLista = this.cantElementos;
		Comparable [] arrayEtiquetas = new Comparable [cantElementosLista];
		IElemento first = this.primero;
		int cont = 0;
		while (first != null){
			arrayEtiquetas[cont] = first.getEtiqueta();
			cont++;
			first = first.getSiguiente();
		}
		return arrayEtiquetas;
	}

	/**
	 * Invierte el orden de la lista
	 */
	@Override
	public void invertir() {
		TLista nuevaLista = new TLista();
		this.primero = invertirRecursivo(this.primero, nuevaLista).primero;
		this.ultimo = nuevaLista.ultimo;
		
	}
	
	/**
	 * Metodo auxiliar recursivo para invertir una lista
	 * @param elemento elemento a invertir
	 * @param lista lista a invertir
	 * @return lista invertida
	 */
	public TLista invertirRecursivo(IElemento elemento, TLista lista) {
		if (elemento == null)
			return lista;
		else {
				IElemento aux = new TElemento(elemento.getEtiqueta(), null);
				lista.insertarAlPrincipio(aux);
				return invertirRecursivo(elemento.getSiguiente(), lista);
		}
	}

	/**
	 * Retorna el elemento anterior al elemento de etiqueta unaEtiqueta, en caso contrario retorna null
	 * @param etiqueta del elemento a buscar
	 * @return elemento anterior al elemento de etiqueta unaEtiqueta
	 */
	@Override
	public IElemento anterior(Comparable unaEtiqueta) {
		IElemento elem = buscar(unaEtiqueta);
		if (elem == null) {
			return null;
		} 
		else {
				if (this.primero.getEtiqueta().equals(unaEtiqueta))
					return null;
				else {
						IElemento aux = this.primero;
						while (!aux.getSiguiente().getEtiqueta().equals(unaEtiqueta)) {
							aux = aux.getSiguiente();
						}
						return aux;
					}
			}
	}

	/**
	 * Retorna un string con las etiquetas de la lista concatenadas con el SEPARADOR_ELEMENTOS_IMPRESOS
	 *@return String con las etiquetas de la lista
	 */
	@Override
	public String imprimirEtiquetas() {
		IElemento aux = this.primero;
		String salida = "";
		while ((aux != null) && (aux.getSiguiente() != null)) {
			salida += aux.getEtiqueta().toString() + SEPARADOR_ELEMENTOS_IMPRESOS;
			aux=aux.getSiguiente();
		}
		if (aux != null){
			salida += aux.getEtiqueta().toString();
		}
		return salida;
	}
	
	/**
	 * Ordena los elementos de la lista
	 */
	@Override
	public void ordenar() {
		TLista nuevaLista = new TLista();
		IElemento first = this.primero;
		while (first != null) {
			IElemento nuevoElemento = new TElemento(first.getEtiqueta(),first.getDatos());
			nuevaLista.insertarOrdenado(nuevoElemento);
			first = first.getSiguiente();
		}
		this.primero = nuevaLista.primero;
		this.ultimo = nuevaLista.ultimo;
	}

	/**
	 * Quita el primer elemento de la lista y lo retorna, si la lista es vacia retorna null
	 * @return elemento eliminado de la lista
	 */
	@Override
	public IElemento quitarPrimero() {
		if (this.esVacia())
			return null;
		else{
				IElemento nodo = this.primero;
				this.primero = nodo.getSiguiente();
				this.cantElementos--;
				return nodo;
		}
	}
	
	/**
	 * Metodo auxiliar que indica si la lista esta ordenada, en caso de estarla retorna true, false en caso contrario
	 * @return true si la lista esta ordenada, false en caso contrario
	 */
	@SuppressWarnings("unchecked")
	public boolean estaOrdenada() {
		if (this.esVacia())
			return true;
		else {
			IElemento aux = this.primero;
			while (aux.getSiguiente() != null) {
				if (aux.getEtiqueta().compareTo(aux.getSiguiente().getEtiqueta()) > 0)
					return false;
				aux = aux.getSiguiente();
			}
			return true;
		}
	}
}
